package sorts

func InsertionSort(arr []int) []int {
	for curIdx := 1; curIdx < len(arr); curIdx++ {
		temp := arr[curIdx]
		tempIdx := curIdx
		for ; tempIdx > 0 && arr[tempIdx - 1] >= temp; tempIdx-- {
			arr[tempIdx] = arr[tempIdx - 1];
		}
		arr[tempIdx] = temp
	}

	return arr
}

